package com.algrithom.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 格雷码
 *
 * @author think
 * @version 1.0.0
 * @since 2019/12/22
 */
public class GrayOper {
    
    public static void main(String[] args){
        System.out.println(String.join(",",getGray(3)));
        System.out.println(grayCode(3).stream().map(String::valueOf).collect(Collectors.joining(",")));
    }
    
    /**
     * 递归解法
     *
     * @param n 位数
     * @return 格雷码数组
     */
    private static String[] getGray(int n){
        // 先创建数组
        int size = (int)Math.pow(2,n);
        String[] arr = new String[size];
        
        if (n == 1) {
            arr[0] = "0";
            arr[1] = "1";
            return arr;
        }
        
        // n-1时的数组
        String[] pre = getGray(n - 1);
        
        for (int i = 0; i < pre.length; i++) {
            arr[i] = "0" + pre[i];
            arr[arr.length - 1 - i] = "1" + pre[i];
        }
        return arr;
    }
    
    /**
     * 动态规划解法
     *
     * @param n 位数
     * @return 格雷码数组
     */
    private static List<Integer> grayCode(int n){
        List<Integer> gray = new ArrayList<>();
        // 初始化 n = 0 的解
        gray.add(0);
        for (int i = 0; i < n; i++) {
            // 要加的数
            int add = 1 << i;
            // 倒序遍历，并且加上一个值添加到结果中
            for (int j = gray.size() - 1; j >= 0; j--) {
                gray.add(gray.get(j) + add);
            }
        }
        return gray;
    }
}
